package solutions.leetcode.normal;

import solutions.lib.BaseSolution;
import solutions.lib.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/">1379. 找出克隆二叉树中的相同节点</a>
 */
public class Solution1379 extends BaseSolution {

    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(cloned);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == target) {
                return node;
            } else {
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Solution1379 solution = new Solution1379();
    }
}